package com.awei.study.dataStructure.queue;

import com.awei.study.dataStructure.queue.abs.Priority;
import com.awei.study.dataStructure.queue.abs.Queue;

import java.util.Iterator;

/**
 * @Author liweilong
 * @Date 2023/5/25 15:27
 */
public class Priority_Queue_Head_Big<E extends Priority> implements Queue<E>,Iterable<E> {

    Priority[] array;
    int size = 0;

    public Priority_Queue_Head_Big(int capacity) {
        this.array = new Priority[capacity];
    }

    @Override
    public boolean offer(E value) {
        if(isFull()) return false;
        int child = size;
        int parent = (child - 1) / 2;
//        System.out.println(child);
//        System.out.println(parent);
        while(child > 0 && value.priority() > array[parent].priority()) {
//            System.out.println(child);
//            System.out.println(parent);
            array[child] = array[parent];
            child = parent;
            parent = (child - 1) / 2;
        }
        array[child] =value;
        size++;
        return true;
    }

    @Override
    public E poll() {
        if(isEmpty()) return null;
        Priority e = array[0];
        swap(0,size - 1 );   //交换头尾

        down(0);    //头节点下沉
        array[size] = null;
        size--;
        return (E) e;
    }

    private void down(int parent) {
        int left = parent * 2 + 1;
        int right = left + 1;
        int max = parent;
        if(left < size && array[left].priority() > array[max].priority()) {
            max = left;
        }
        if(right < size && array[right].priority() > array[max].priority()) {
            max = right;
        }
        if(max != parent) {
            swap(parent,max);
            down(max);
        }

    }

    private void swap(int i,int j) {
        Priority t = array[i];
        array[i] = array[j];
        array[j] = t;
    }
    @Override
    public E peek() {
        if(isEmpty()) return null;
        return (E) array[0];
    }

    @Override
    public boolean isFull() {
        return size == array.length;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public Iterator<E> iterator() {
        return new Iterator<E>() {
            int p = 0;
            @Override
            public boolean hasNext() {
                return p < size;
            }

            @Override
            public E next() {
                Priority value = array[p];
                p++;
                return (E) value;
            }
        };
    }
}
